#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include "omp.h"
//#include <iostream>
// #include <algorithm>  //
// #include <cmath>
// #include <iostream>
// #include <string>
// #include <thread>
//#include <boost/thread.hpp>

void imageSmoothing_raw(int** img)
{
    for(int j = 1; j < 1920; j++)
    {
        for (int i = 1; i < 1080; i++)
        {
            img[i][j] = (img[i-1][j] + img[i+1][j]+img[i][j-1] + img[i][j+1] ) / 4; 
            //取某个像素周围四个点的平均值
            //这玩意为什么能跑？？？？？？？？？？？？
        }
    }
}
void imageSmoothing(int** img)
{
    for(int j = 1; j <= 1080; j++)
    {
        for (int i = 1; i <= 1920; i++)
        {
            img[i][j] = (img[i-1][j] + img[i+1][j]+img[i][j-1] + img[i][j+1] ) / 4; 
            //取某个像素周围四个点的平均值
        }
    }
}

void imageSmoothing_CPUoptimize(int **img) //面向CPU的优化（循环展开）
{
    for(int j = 1; j <= 1080; j++)
    {
        for (int i = 1; i <= 1920; i+=6)
        {
            img[i][j] = (img[i-1][j] + img[i+1][j]+img[i][j-1] + img[i][j+1] ) / 4; 
            img[i+1][j] = (img[i][j] + img[i+2][j]+img[i+1][j-1] + img[i+1][j+1] ) / 4; 
            img[i+2][j] = (img[i+1][j] + img[i+3][j]+img[i+2][j-1] + img[i+2][j+1] ) / 4; 
            img[i+3][j] = (img[i+2][j] + img[i+4][j]+img[i+3][j-1] + img[i+3][j+1] ) / 4; 
            img[i+4][j] = (img[i+3][j] + img[i+5][j]+img[i+4][j-1] + img[i+4][j+1] ) / 4; 
            img[i+5][j] = (img[i+4][j] + img[i+6][j]+img[i+5][j-1] + img[i+5][j+1] ) / 4; 
            //程序的空间局部性不佳
        }
    }
}

void imageSmoothing_CacheOptimize(int **img) //面向Cache的优化（分块处理）
{
    for(int i = 1; i <= 1920; i++)
    {
        for (int j = 1; j <= 1080; j++)
        {
            img[i][j] = (img[i-1][j] + img[i+1][j]+img[i][j-1] + img[i][j+1] ) / 4; 
            //改善了空间局部性，顺序读入内存等效于教程中面向cache的优化
        }
    }
}

void imageSmoothing_NormalOptimize(int **img) //针对复杂运算简化的优化
{
    for(int j = 1; j <= 1080; j++)
    {
        for (int i = 1; i <= 1920; i++)
        {
            img[i][j] = (img[i-1][j] + img[i+1][j]+img[i][j-1] + img[i][j+1] ) >> 2; 
            //取某个像素周围四个点的平均值
        }
    }
}

void imageSmoothing_AllOptimize(int **img) //全部手段
{
    for(int i = 1; i <= 1920; i++)
    {
        for (int j = 1; j <= 1080; j+=12)
        {
            img[i][j] = (img[i-1][j] + img[i+1][j]+img[i][j-1] + img[i][j+1] ) >> 2; 
            img[i][j+1] = (img[i-1][j+1] + img[i+1][j+1]+img[i][j] + img[i][j+2] ) >> 2; 
            img[i][j+2] = (img[i-1][j+2] + img[i+1][j+2]+img[i][j+1] + img[i][j+3] ) >> 2; 
            img[i][j+3] = (img[i-1][j+3] + img[i+1][j+3]+img[i][j+2] + img[i][j+4] ) >> 2; 
            img[i][j+4] = (img[i-1][j+4] + img[i+1][j+4]+img[i][j+3] + img[i][j+5] ) >> 2; 
            img[i][j+5] = (img[i-1][j+5] + img[i+1][j+5]+img[i][j+4] + img[i][j+6] ) >> 2; 
            img[i][j+6] = (img[i-1][j+6] + img[i+1][j+6]+img[i][j+5] + img[i][j+7] ) >> 2; 
            img[i][j+7] = (img[i-1][j+7] + img[i+1][j+7]+img[i][j+6] + img[i][j+8] ) >> 2; 
            img[i][j+8] = (img[i-1][j+8] + img[i+1][j+8]+img[i][j+7] + img[i][j+9] ) >> 2; 
            img[i][j+9] = (img[i-1][j+9] + img[i+1][j+9]+img[i][j+8] + img[i][j+10] ) >> 2; 
            img[i][j+10] = (img[i-1][j+10] + img[i+1][j+10]+img[i][j+9] + img[i][j+11] ) >> 2; 
            img[i][j+11] = (img[i-1][j+11] + img[i+1][j+11]+img[i][j+10] + img[i][j+12] ) >> 2; 
        }
    }
}




int main()
{   
   
    int** img = (int**)malloc(sizeof(int*) * 1922);//在1920*1080的图像边缘增加一圈像素，防止滑窗溢出图像
    srand((int)time(NULL));//随机种子
    int number=0;
    
    for (int i = 0; i < 1922; i++)
    {
        img[i] = (int*)malloc(sizeof(int) * 1082);//在1920*1080的图像边缘增加一圈像素，防止滑窗溢出图像
        for (int j = 0; j < 1082; j++)  //为每个图像添加高斯噪声
        {
            number = rand();
            img[i][j] = number;
        }
    }   
    
    clock_t startTimeVal = clock();
    for(int i = 0; i < 10000; i++)
    {
        imageSmoothing(img);
    }
    clock_t finishTimeVal = clock();
    printf("未作优化 执行10000次用时: %f 秒\n", (double)(finishTimeVal - startTimeVal) / CLOCKS_PER_SEC);

    for (int i = 0; i < 1922; i++)
    {
        for (int j = 0; j < 1082; j++)  //为每个图像添加高斯噪声
        {
            number = rand();
            img[i][j] = number;
        }
    }  

    startTimeVal = clock();
    for(int i = 0; i < 10000; i++)
    {
        imageSmoothing_CPUoptimize(img);
    }
    finishTimeVal = clock();
    printf("循环优化 执行10000次用时: %f 秒\n", (double)(finishTimeVal - startTimeVal) / CLOCKS_PER_SEC);

    for (int i = 0; i < 1922; i++)
    {
        for (int j = 0; j < 1082; j++)  //为每个图像添加高斯噪声
        {
            number = rand();
            img[i][j] = number;
        }
    }  

    startTimeVal = clock();
    for(int i = 0; i < 10000; i++)
    {
        imageSmoothing_CacheOptimize(img);
    }
    finishTimeVal = clock();
    printf("缓存优化 执行10000次用时: %f 秒\n", (double)(finishTimeVal - startTimeVal) / CLOCKS_PER_SEC);

    for (int i = 0; i < 1922; i++)
    {
        for (int j = 0; j < 1082; j++)  //为每个图像添加高斯噪声
        {
            number = rand();
            img[i][j] = number;
        }
    }  

    startTimeVal = clock();
    for(int i = 0; i < 10000; i++)
    {
        imageSmoothing_NormalOptimize(img);
    }
    finishTimeVal = clock();
    printf("运算符优化 执行10000次用时: %f 秒\n", (double)(finishTimeVal - startTimeVal) / CLOCKS_PER_SEC);

    for (int i = 0; i < 1922; i++)
    {
        for (int j = 0; j < 1082; j++)  //为每个图像添加高斯噪声
        {
            number = rand();
            img[i][j] = number;
        }
    }  

    startTimeVal = clock();
    for(int i = 0; i < 10000; i++)
    {
        imageSmoothing_AllOptimize(img);
    }
    finishTimeVal = clock();
    printf("全部优化 执行10000次用时: %f 秒\n", (double)(finishTimeVal - startTimeVal) / CLOCKS_PER_SEC);

    for (int i = 0; i < 1922; i++)
    {
        for (int j = 0; j < 1082; j++)  //为每个图像添加高斯噪声
        {
            number = rand();
            img[i][j] = number;
        }
    }  





    double startTimeVal8 = omp_get_wtime();
    {
        #pragma omp parallel for num_threads(4)//将循环分为4个线程
        for(int i = 0; i < 10000; i++)
        {
            imageSmoothing(img);
        }
    }
    double finishTimeVal8 = omp_get_wtime();
    printf("多线程优化 执行10000次用时: %f 秒\n", (double)(finishTimeVal8 - startTimeVal8));

    for (int i = 0; i < 1922; i++)
    {
        for (int j = 0; j < 1082; j++)  //为每个图像添加高斯噪声
        {
            number = rand();
            img[i][j] = number;
        }
    }  

    startTimeVal8 = omp_get_wtime();
    {
        #pragma omp parallel for num_threads(4)//将循环分为4个线程
        for(int i = 0; i < 10000; i++)
        {
            imageSmoothing_AllOptimize(img);
        }
    }
    finishTimeVal8 = omp_get_wtime();
    printf("多线程全优化 执行10000次用时: %f 秒\n", (double)(finishTimeVal8 - startTimeVal8));
    return 0;
}

